Ćwiczenia/3. Ćwiczenia/Zadanie 5. (Struktura z wstawianiem, usuwaniem maksimum i minimum w czasie O(log n)).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Proszę przedstawić W jaki sposób zrealizować strukturę danych, która pozwala wykonywać operacje:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Insert"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. RemoveMin"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. RemoveMax"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### tak, żeby wszystkie operacje działały w czasie $ O(log(n)) $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Funkcja pomocnicza formatująca kompletne drzewo binarne"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def complete_tree_string(values):\n",
    "    if values:\n",
    "        just = 0\n",
    "        data = []\n",
    "\n",
    "        limit = 1\n",
    "        values_row = []\n",
    "        branches_row = []\n",
    "        prev_nodes = 0\n",
    "\n",
    "        for i in range(1, len(values) + 1):\n",
    "            curr_nodes = i - prev_nodes\n",
    "            val_str = str(values[i-1])\n",
    "            just = max(just, len(val_str))\n",
    "            values_row.append(val_str)\n",
    "            right_child_idx = 2 * i\n",
    "            left_child_idx = right_child_idx - 1\n",
    "            if left_child_idx < len(values):\n",
    "                branches_row.append('/')\n",
    "            if right_child_idx < len(values):\n",
    "                branches_row.append('\\\\')\n",
    "\n",
    "            if curr_nodes == limit: \n",
    "                prev_nodes = i\n",
    "                limit *= 2\n",
    "                data.append([values_row, branches_row])\n",
    "                values_row = []\n",
    "                branches_row = []\n",
    "\n",
    "        if values_row:\n",
    "            data.append([values_row, branches_row])\n",
    "\n",
    "        begin_sep = sep = 3 if just % 2 else 2\n",
    "        data_iter = iter(data[::-1])\n",
    "        result = [''] * (len(data) * 2 - 1)\n",
    "        result[-1] = (' ' * sep).join(val.center(just) for val in next(data_iter)[0])\n",
    "\n",
    "        # Format the tree string\n",
    "        for i, (values, branches) in enumerate(data_iter):\n",
    "            mul = 2 * i + 1\n",
    "            # Values\n",
    "            indent = (2 ** (i + 1) - 1) * (just + begin_sep) // 2\n",
    "            sep = 2 * sep + just\n",
    "            result[-(mul + 2)] = f\"{' ' * indent}{(' ' * sep).join(val.center(just) for val in values)}\"\n",
    "            # Branches\n",
    "            branch_indent = (3 * indent + just) // 4\n",
    "            branches_row = []\n",
    "            d_indent = indent - branch_indent\n",
    "            branches_sep = ' ' * (2 * (d_indent - 1) + just)\n",
    "            for i in range(0, len(branches), 2):\n",
    "                branches_row.append(f\"{branches[i]}{branches_sep}{branches[i + 1] if i + 1 < len(branches) else ''}\")\n",
    "            result[-(mul + 1)] = f\"{' ' * branch_indent}{(' ' * (sep - 2 * d_indent)).join(branches_row)}\"\n",
    "\n",
    "        return '\\n'.join(result)\n",
    "    else:\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu (obiektowa)\n",
    "#### Innej już mi się nie chce robić"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class CrazyHeap:\n",
    "    def __init__(self, values=None):\n",
    "        if values:\n",
    "            # We make a copy of values in order not to modify them\n",
    "            self.min_heap = [[i, values[i]] for i in range(len(values))]\n",
    "            self.max_heap = [[i, values[i]] for i in range(len(values))]\n",
    "            self.build_heaps()\n",
    "        else:\n",
    "            self.min_heap = []\n",
    "            self.max_heap = []\n",
    "\n",
    "    def __str__(self):\n",
    "        max_str = complete_tree_string(self.max_heap)\n",
    "        min_str = complete_tree_string(self.min_heap)\n",
    "        return f\"Max Heap:\\n{max_str}\\n\\nMin Heap:\\n{min_str}\"\n",
    "\n",
    "    def __bool__(self):\n",
    "        return bool(self.max_heap)  # We can also use bool(self.min_heap)\n",
    "\n",
    "    @property\n",
    "    def heap_size(self):\n",
    "        return len(self.max_heap)  # We can also use len(self.min_heap)\n",
    "\n",
    "    @staticmethod\n",
    "    def parent_idx(curr_idx):\n",
    "        return (curr_idx - 1) // 2\n",
    "\n",
    "    @staticmethod\n",
    "    def left_child_idx(curr_idx):\n",
    "        return curr_idx * 2 + 1\n",
    "\n",
    "    @staticmethod\n",
    "    def right_child_idx(curr_idx):\n",
    "        return curr_idx * 2 + 2\n",
    "\n",
    "    def get_max(self) -> object:\n",
    "        return None if not self.max_heap else self.max_heap[0][1]\n",
    "\n",
    "    def get_min(self) -> object:\n",
    "        return None if not self.min_heap else self.min_heap[0][1]\n",
    "\n",
    "    def insert(self, val: object):\n",
    "        # Add values at the end of both heaps\n",
    "        insert_idx = self.heap_size\n",
    "        self.max_heap.append([insert_idx, val])\n",
    "        self.min_heap.append([insert_idx, val])\n",
    "        # If a value added is not lower than the greatest value previously stored,\n",
    "        # fix only the Max Heap as the Min Heap wouldn't be violated\n",
    "        if val >= self.get_max():\n",
    "            self._heapify_max_up(insert_idx)\n",
    "        # If a value is not greater than the lowest value previously stored,\n",
    "        # fix only the Min Heap as the Max Heap wouldn't be violated\n",
    "        elif val <= self.get_min():\n",
    "            self._heapify_min_up(insert_idx)\n",
    "        # If a value is between the greatest and the lowest value previously stored,\n",
    "        # we have to fix both heaps\n",
    "        else:\n",
    "            self._heapify_max_up(insert_idx)\n",
    "            self._heapify_min_up(insert_idx)\n",
    "\n",
    "    def remove_max(self) -> object:\n",
    "        if not self:\n",
    "            raise IndexError(f'remove_max from an empty {self.__class__.__name__}')\n",
    "        if self.heap_size == 1:\n",
    "            removed = self.max_heap.pop()  # We can either pop it from the Max or from the Min Heap\n",
    "            self.min_heap.clear()\n",
    "        else:\n",
    "            # Store removed entry (a root of the Max Heap)\n",
    "            removed = self.max_heap[0]\n",
    "            # Remove this entry from the Max Heap and fix indices stored in the Min Heap\n",
    "            self.max_heap[0] = self.max_heap.pop()\n",
    "            # Remove this entry from the Min Heap (it always will be one of leaves an index of which\n",
    "            # we have stored as the first value of the entry removed from the Max Heap)\n",
    "            min_heap_last = self.min_heap[-1]\n",
    "            # If we have to remove a leaf which is not the last one leaf of the Min Heap, we have\n",
    "            # to fix indices stored in the Max Heap\n",
    "            if min_heap_last is not self.min_heap[removed[0]]:\n",
    "                self.min_heap[removed[0]] = min_heap_last\n",
    "                # If the last node of the Min Heap wasn't the same as the last node of the Max Heap,\n",
    "                # we can update index of a node of an index min_heap_last[0] to a proper value\n",
    "                if min_heap_last[0] < len(self.max_heap):\n",
    "                    self.max_heap[min_heap_last[0]][0] = removed[0]\n",
    "                # Otherwise the node removed must be a root node, so we update an index stored by it\n",
    "                else:\n",
    "                    self.max_heap[0][0] = removed[0]\n",
    "            # Fix indices stored in entries of the Min Heap which refer to the position of the\n",
    "            # entry moved to a root position of the Max Heap (it was previously the last leaf)\n",
    "            self.min_heap[self.max_heap[0][0]][0] = 0\n",
    "            self.min_heap.pop()\n",
    "            # Now we have to heapify down the Max Heap as we inserted a new node on the root position\n",
    "            self._heapify_max_down(0, self.heap_size)\n",
    "        return removed[1]  # Return only a value\n",
    "\n",
    "    def remove_min(self) -> object:\n",
    "        if not self:\n",
    "            raise IndexError(f'remove_min from an empty {self.__class__.__name__}')\n",
    "        if self.heap_size == 1:\n",
    "            removed = self.max_heap.pop()  # We can either pop it from the Max or from the Min Heap\n",
    "            self.min_heap.clear()\n",
    "        else:\n",
    "            # Store removed entry (a root of the Min Heap)\n",
    "            removed = self.min_heap[0]\n",
    "            # Remove this entry from the Min Heap and fix indices stored in the Max Heap\n",
    "            self.min_heap[0] = self.min_heap.pop()\n",
    "            # Remove this entry from the Max Heap (it always will be one of leaves an index of which\n",
    "            # we have stored as the first value of the entry removed from the Min Heap)\n",
    "            max_heap_last = self.max_heap[-1]\n",
    "            # If we have to remove a leaf which is not the last one leaf of the Max Heap, we have\n",
    "            # to fix indices stored in the Min Heap\n",
    "            if max_heap_last is not self.max_heap[removed[0]]:\n",
    "                self.max_heap[removed[0]] = max_heap_last\n",
    "                # If the last node of the Max Heap wasn't the same as the last node of the Min Heap,\n",
    "                # we can update index of a node of an index max_heap_last[0] to a proper value\n",
    "                if max_heap_last[0] < len(self.min_heap):\n",
    "                    self.min_heap[max_heap_last[0]][0] = removed[0]\n",
    "                # Otherwise the node removed must be a root node, so we update an index stored by it\n",
    "                else:\n",
    "                    self.min_heap[0][0] = removed[0]\n",
    "            # Fix indices stored in entries of the Max Heap which refer to the position of the\n",
    "            # entry moved to a root position of the Min Heap (it was previously the last leaf)\n",
    "            self.max_heap[self.min_heap[0][0]][0] = 0\n",
    "            self.max_heap.pop()\n",
    "            # Now we have to heapify down the Min Heap as we inserted a new node on the root position\n",
    "            self._heapify_min_down(0, self.heap_size)\n",
    "        return removed[1]  # Return only a value\n",
    "\n",
    "    def swap(self, heap, i, j):\n",
    "        # Swap nodes (both values and indices) in the heap specified\n",
    "        heap[i], heap[j] = heap[j], heap[i]\n",
    "        # Store indices which show where are swapped values stored in a second heap\n",
    "        i = heap[i][0]\n",
    "        j = heap[j][0]\n",
    "        # Update indices stored in the second heap which wasn't modified\n",
    "        if heap is self.max_heap:\n",
    "            # Update entries (swap indices only) in the Min Heap\n",
    "            self.min_heap[i][0], self.min_heap[j][0] = self.min_heap[j][0], self.min_heap[i][0]\n",
    "        else:\n",
    "            # Update entries (swap indices only) in the Max Heap\n",
    "            self.max_heap[i][0], self.max_heap[j][0] = self.max_heap[j][0], self.max_heap[i][0]\n",
    "\n",
    "    def build_heaps(self):\n",
    "        self._build_max_heap()\n",
    "        self._build_min_heap()\n",
    "            \n",
    "    def _heapify_max_up(self, curr_idx, end_idx=0):  # O(log n)\n",
    "        while curr_idx > end_idx:\n",
    "            parent_idx = self.parent_idx(curr_idx)\n",
    "            # Compare values of the nodes\n",
    "            if self.max_heap[curr_idx][1] > self.max_heap[parent_idx][1]:\n",
    "                self.swap(self.max_heap, curr_idx, parent_idx)\n",
    "            curr_idx = parent_idx\n",
    "\n",
    "    def _heapify_min_up(self, curr_idx, end_idx=0):  # O(log n)\n",
    "        while curr_idx > end_idx:\n",
    "            parent_idx = self.parent_idx(curr_idx)\n",
    "            # Compare values of the nodes\n",
    "            if self.min_heap[curr_idx][1] < self.min_heap[parent_idx][1]:\n",
    "                self.swap(self.min_heap, curr_idx, parent_idx)\n",
    "            curr_idx = parent_idx\n",
    "\n",
    "    def _heapify_max_down(self, curr_idx, end_idx):  # O(log n)\n",
    "        # Loop till the current node has a child larger than itself\n",
    "        # We assume that when we enter a node which both children are\n",
    "        # smaller than this node, a subtree which a current node is a\n",
    "        # root of must fulfill a max-heap property\n",
    "        while True:\n",
    "            l = self.left_child_idx(curr_idx)\n",
    "            r = self.right_child_idx(curr_idx)\n",
    "            largest_idx = curr_idx\n",
    "\n",
    "            if l < end_idx:\n",
    "                if self.max_heap[l][1] > self.max_heap[curr_idx][1]:\n",
    "                    largest_idx = l\n",
    "                if r < end_idx and self.max_heap[r][1] > self.max_heap[largest_idx][1]:\n",
    "                    largest_idx = r\n",
    "\n",
    "            if largest_idx != curr_idx:\n",
    "                self.swap(self.max_heap, curr_idx, largest_idx)\n",
    "                curr_idx = largest_idx\n",
    "            else:\n",
    "                break\n",
    "\n",
    "    def _heapify_min_down(self, curr_idx, end_idx):  # O(log n)\n",
    "        # Loop till the current node has a child smaller than itself\n",
    "        # We assume that when we enter a node which both children are\n",
    "        # larger than this node, a subtree which a current node is a\n",
    "        # root of must fulfill a min-heap property\n",
    "        while True:\n",
    "            l = self.left_child_idx(curr_idx)\n",
    "            r = self.right_child_idx(curr_idx)\n",
    "            smallest_idx = curr_idx\n",
    "\n",
    "            if l < end_idx:\n",
    "                if self.min_heap[l][1] < self.min_heap[curr_idx][1]:\n",
    "                    smallest_idx = l\n",
    "                if r < end_idx and self.min_heap[r][1] < self.min_heap[smallest_idx][1]:\n",
    "                    smallest_idx = r\n",
    "\n",
    "            if smallest_idx != curr_idx:\n",
    "                self.swap(self.min_heap, curr_idx, smallest_idx)\n",
    "                curr_idx = smallest_idx\n",
    "            else:\n",
    "                break\n",
    "                \n",
    "    def _build_max_heap(self):   # O (n)\n",
    "        for i in range(self.heap_size // 2 - 1, -1, -1):\n",
    "            self._heapify_max_down(i, self.heap_size)\n",
    "            \n",
    "    def _build_min_heap(self):   # O (n)\n",
    "        for i in range(self.heap_size // 2 - 1, -1, -1):\n",
    "            self._heapify_min_down(i, self.heap_size)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Max Heap:\n",
      "[0, 3]\n",
      "\n",
      "Min Heap:\n",
      "[0, 3]\n",
      "\n",
      "\n",
      "\n",
      "Max Heap:\n",
      "    [1, 8]\n",
      "    /    \n",
      "[0, 3]\n",
      "\n",
      "Min Heap:\n",
      "    [1, 3]\n",
      "    /    \n",
      "[0, 8]\n",
      "\n",
      "\n",
      "\n",
      "Max Heap:\n",
      "    [1, 8]\n",
      "    /    \\\n",
      "[0, 3]  [2, 6]\n",
      "\n",
      "Min Heap:\n",
      "    [1, 3]\n",
      "    /    \\\n",
      "[0, 8]  [2, 6]\n",
      "\n",
      "\n",
      "\n",
      "Max Heap:\n",
      "            [3, 8]\n",
      "          /        \\\n",
      "    [1, 3]          [2, 6]\n",
      "    /    \n",
      "[0, 2]\n",
      "\n",
      "Min Heap:\n",
      "            [3, 2]\n",
      "          /        \\\n",
      "    [1, 3]          [2, 6]\n",
      "    /    \n",
      "[0, 8]\n",
      "\n",
      "\n",
      "\n",
      "Max Heap:\n",
      "            [3, 8]\n",
      "          /        \\\n",
      "    [4, 3]          [2, 6]\n",
      "    /    \\\n",
      "[1, 2]  [0, 1]\n",
      "\n",
      "Min Heap:\n",
      "            [4, 1]\n",
      "          /        \\\n",
      "    [3, 2]          [2, 6]\n",
      "    /    \\\n",
      "[0, 8]  [1, 3]\n",
      "\n",
      "\n",
      "\n",
      "Max Heap:\n",
      "            [3, 8]\n",
      "          /        \\\n",
      "    [4, 3]          [5, 6]\n",
      "    /    \\          /    \n",
      "[1, 2]  [2, 1]  [0, 0]\n",
      "\n",
      "Min Heap:\n",
      "            [5, 0]\n",
      "          /        \\\n",
      "    [3, 2]          [4, 1]\n",
      "    /    \\          /    \n",
      "[0, 8]  [1, 3]  [2, 6]\n",
      "\n",
      "\n",
      "\n",
      "Max Heap:\n",
      "            [3, 8]\n",
      "          /        \\\n",
      "    [4, 3]          [5, 6]\n",
      "    /    \\          /    \\\n",
      "[1, 2]  [2, 1]  [0, 0]  [6, 5]\n",
      "\n",
      "Min Heap:\n",
      "            [5, 0]\n",
      "          /        \\\n",
      "    [3, 2]          [4, 1]\n",
      "    /    \\          /    \\\n",
      "[0, 8]  [1, 3]  [2, 6]  [6, 5]\n",
      "\n",
      "\n",
      "\n",
      "Max Heap:\n",
      "                            [7, 9]\n",
      "                      /                \\\n",
      "            [3, 8]                          [5, 6]\n",
      "          /        \\                      /        \\\n",
      "    [4, 3]          [2, 1]          [0, 0]          [6, 5]\n",
      "    /    \n",
      "[1, 2]\n",
      "\n",
      "Min Heap:\n",
      "                            [5, 0]\n",
      "                      /                \\\n",
      "            [7, 2]                          [4, 1]\n",
      "          /        \\                      /        \\\n",
      "    [1, 8]          [3, 3]          [2, 6]          [6, 5]\n",
      "    /    \n",
      "[0, 9]\n",
      "\n",
      "\n",
      "\n",
      "Max Heap:\n",
      "                            [7, 9]\n",
      "                      /                \\\n",
      "            [8, 8]                          [5, 6]\n",
      "          /        \\                      /        \\\n",
      "    [3, 7]          [2, 1]          [0, 0]          [6, 5]\n",
      "    /    \\\n",
      "[1, 2]  [4, 3]\n",
      "\n",
      "Min Heap:\n",
      "                            [5, 0]\n",
      "                      /                \\\n",
      "            [7, 2]                          [4, 1]\n",
      "          /        \\                      /        \\\n",
      "    [3, 7]          [8, 3]          [2, 6]          [6, 5]\n",
      "    /    \\\n",
      "[0, 9]  [1, 8]\n",
      "\n",
      "\n",
      "\n",
      "Max Heap:\n",
      "                            [7, 9]\n",
      "                      /                \\\n",
      "            [8, 8]                          [5, 6]\n",
      "          /        \\                      /        \\\n",
      "    [3, 7]          [9, 4]          [0, 0]          [6, 5]\n",
      "    /    \\          /    \n",
      "[1, 2]  [4, 3]  [2, 1]\n",
      "\n",
      "Min Heap:\n",
      "                            [5, 0]\n",
      "                      /                \\\n",
      "            [7, 2]                          [9, 1]\n",
      "          /        \\                      /        \\\n",
      "    [3, 7]          [8, 3]          [2, 6]          [6, 5]\n",
      "    /    \\          /    \n",
      "[0, 9]  [1, 8]  [4, 4]\n",
      "\n",
      "\n",
      "\n",
      "Removing max:\n",
      "9 8 7 6 5 4 3 2 1 0 \n",
      "Removing min:\n",
      "0 1 2 3 4 5 6 7 8 9 \n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "lst = list(range(10))\n",
    "random.shuffle(lst)\n",
    "ch = CrazyHeap()\n",
    "for i in lst:\n",
    "    ch.insert(i)\n",
    "    print(ch, end='\\n\\n\\n\\n')\n",
    "\n",
    "print('Removing max:')\n",
    "while ch:\n",
    "    print(ch.remove_max(), end=' ')\n",
    "print()\n",
    "    \n",
    "    \n",
    "for i in lst:\n",
    "    ch.insert(i)\n",
    "print('Removing min:')\n",
    "while ch:\n",
    "#     print(ch)\n",
    "    print(ch.remove_min(), end=' ')\n",
    "print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Max Heap:\n",
      "                            [5, 9]\n",
      "                      /                \\\n",
      "            [7, 8]                          [6, 4]\n",
      "          /        \\                      /        \\\n",
      "    [8, 7]          [9, 6]          [0, 0]          [2, 3]\n",
      "    /    \\          /    \n",
      "[1, 1]  [3, 2]  [4, 5]\n",
      "\n",
      "Min Heap:\n",
      "                            [5, 0]\n",
      "                      /                \\\n",
      "            [7, 1]                          [6, 3]\n",
      "          /        \\                      /        \\\n",
      "    [8, 2]          [9, 5]          [0, 9]          [2, 4]\n",
      "    /    \\          /    \n",
      "[1, 8]  [3, 7]  [4, 6]\n",
      "Removing max:\n",
      "0 1 2 3 4 5 6 7 8 9 \n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "lst = list(range(10))\n",
    "random.shuffle(lst)\n",
    "ch = CrazyHeap(lst)\n",
    "\n",
    "print(ch)\n",
    "\n",
    "print('Removing max:')\n",
    "while ch:\n",
    "    print(ch.remove_min(), end=' ')\n",
    "print()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}